package com.dycong.common.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
 * <p>
 * 说明：
 * <p>
 * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
 * <p>
 * 示例 1:
 * <p>
 * 输入: [2,2,3,2]
 * 输出: 3
 * 示例 2:
 * <p>
 * 输入: [0,1,0,1,0,1,99]
 * 输出: 99
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/single-number-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class SingleNumber__II_137 {

    // TODO: 2019/12/23 位运算符—与（&）、非（~）、或（|）、异或（^）
    // TODO: 2019/12/23 >>(向右位移) 针对二进制，转换成二进制后向右移动3位，>>>(无符号右移)  无符号右移，忽略符号位，空位都以0补齐
    public static void main(String[] args) {
        SingleNumber__II_137 singleNumber__ii_137 = new SingleNumber__II_137();
        int[] ints = new int[]{2, 2, 3, 2};
        int[] ints2 = new int[]{0, 1, 0, 1, 0, 1, 99};

        System.out.println(singleNumber__ii_137.singleNumber0(ints));
        System.out.println(singleNumber__ii_137.singleNumber0(ints2));
    }

    /**
     * 3*(a+b+c) - a-a-a-b-b-b-c=2c
     *
     * @param nums
     * @return
     * @see 错误: 因为可以是负数
     */
    public int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();

        for (int i : nums) {
            set.add(i);
        }

        long res = 0;

        for (int i : set) {
            res += 3 * i;
        }

        for (int i : nums) {
            res -= i;
        }
        return (int) (res / 2);
    }

    /**
     * 解法三 位操作
     * 136 题通过异或解决了问题，这道题明显不能用异或了，参考 这里 的一个解法。
     * <p>
     * 我们把数字放眼到二进制形式
     * <p>
     * 假如例子是 1 2 6 1 1 2 2 3 3 3, 3 个 1, 3 个 2, 3 个 3,1 个 6
     * 1 0 0 1
     * 2 0 1 0
     * 6 1 1 0
     * 1 0 0 1
     * 1 0 0 1
     * 2 0 1 0
     * 2 0 1 0
     * 3 0 1 1
     * 3 0 1 1
     * 3 0 1 1
     * 看最右边的一列 1001100111 有 6 个 1
     * 再往前看一列 0110011111 有 7 个 1
     * 再往前看一列 0010000 有 1 个 1
     * 我们只需要把是 3 的倍数的对应列写 0，不是 3 的倍数的对应列写 1
     * 也就是 1 1 0,也就是 6。
     * 原因的话，其实很容易想明白。如果所有数字都出现了 3 次，那么每一列的 1 的个数就一定是 3 的倍数。之所以有的列不是 3 的倍数，就是因为只出现了 1 次的数贡献出了 1。所以所有不是 3 的倍数的列写 1，其他列写 0 ，就找到了这个出现 1 次的数。
     */
    public int singleNumber2(int[] nums) {
        int res = 0;
        //考虑每一位
        for (int i = 0; i < 32; i++) {
            int count = 0;
            //考虑每一个数
            for (int num : nums) {
                //todo 当前位是否是 1,此处使用 >>> 而不是 >> 未免位发生改变
                if ((num >>> i & 1) == 1) {
                    count++;
                }
            }
            //1 的个数是否是 3 的倍数
            if (count % 3 != 0) {
//                res = res + (1 << i);
                res = res | (1 << i);
            }
        }
        return res;

    }


    /*
    public int singleNumber(int[] nums) {
        int one = 0, two = 0, three;
        for (int num : nums) {
            // two的相应的位等于1，表示该位出现2次
            two |= (one & num);
            // one的相应的位等于1，表示该位出现1次
            one ^= num;
            // three的相应的位等于1，表示该位出现3次
            three = (one & two);
            // 如果相应的位出现3次，则该位重置为0
            two &= ~three;
            one &= ~three;
        }
        return one;
    }
     */

    public int singleNumber0(int[] nums) {
        int one = 0, two = 0, three = 0;

        for (int num : nums) {

            two |= (one & num);

            one ^= num;

            three = (one & two);

            one &= ~three;
            two &= ~three;
        }
        return one;
    }
}